/*
 * @Author: lichao 1246877006@qq.com
 * @Date: 2024-09-25 16:24:21
 * @LastEditors: lichao 1246877006@qq.com
 * @LastEditTime: 2024-09-25 19:19:09
 * @FilePath: \algorithm\hello-algo\5 栈与队列\5.2队列.js
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
// 初始化队列
const queue = []

queue.push(1)
queue.push(2)
queue.push(3)
queue.push(4)
queue.push(5)

// 首元素
const peek = queue[0]

// 元素出栈
const pop = queue.shift()

// 队列的长度
const length = pop.length

// 队列是否为空
const empty = length === 0

// 节点类
class Node {
    val;
    next;
    constructor(val, next) {
        this.val = (val === undefined ? null : val)
        this.next = (next === undefined ? null : next)
    }
}

// 基于链表实现队列
class LinkedListQueue {
    #front; // 头节点
    #rear; // 尾节点
    #queueSize = 0

    constructor() {
        this.#front = null
        this.#rear = null
    }

    // 获取对队列长度
    get size() {
        return this.#queueSize
    }

    // 是否为空
    isEmpty() {
        return this.size === 0
    }

    // 入队
    push(num) {
        const node = new Node(num)
        if(!this.#front) {
            // 队列为空则收尾都赋值 node
            this.#front = node
            this.#rear = node
        } else {
            this.#rear.next = node
            this.#rear = node
        }
        this.#queueSize++
    }

    // 出栈
    pop() {
        const num = this.peek()
        this.#front = this.#front.next
        this.#queueSize--
        return num
    }

    // 访问栈顶元素
    peek() {
        if(!this.#queueSize) throw new Error('队列为空')
        return this.#front.val
    }

    toArray() {
        let node = this.#front
        const arr = new Array(this.#queueSize)
        for(let i = 0; i < arr.length; i++) {
            arr[i] = node.val
            node = node.next
        }
        return node
    }
}

// 基于数组实现队列
class ArrayQueue {
    #arr; // 用于存储队列元素的数组
    #front = 0; // 队受指针
    #queSize = 0; // 队列长度

    constructor(capacity) {
        this.#arr = new Array(capacity)
    }

    get capacity() {
        return this.#arr.length
    }

    get size() {
        return this.#queSize
    }

    isEmpty() {
        return this.#queSize === 0
    }

    push(num) {
        if(this.size === this.capacity) throw new Error('队列已满')
        const rear = (this.#front + this.size) % this.capacity
        this.#arr[rear] = num
        this.#queSize++
    }

    pop() {
        const num = this.peek()
        this.#front = (this.#front + 1) % this.capacity
        this.#queSize--
        return num
    }

    peek() {
        if(this.isEmpty()) throw new Error('队列为空')
            return this.#arr[this.#front]
    }

    toArray() {
        const arr = new Array(this.size)
        for(let i = 0, j = this.#front; i < this.size; i++, j++) {
            arr[i] = this.#arr[j % this.capacity]
        }
        return arr
    }
}